package xj.graph2d.graph;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.Comparator;
import java.util.Collections;

public class GraphUtilities {

  static public boolean matchEdgeType(int etype, GraphEdge edge) { 
    if (edge != null) {       
      return (etype < 0) || ((etype & edge.getEdgeType()) != 0);
    }
    return false; 
  }
  
  static public interface EdgePredicate<N extends GraphNode<E>, E extends GraphEdge<N>> {
    public boolean matchEdge(Graph<N, E> graph, E edge, boolean inverted); 
  }

  static public interface NodePredicate<N extends GraphNode<E>, E extends GraphEdge<N>> {
    public boolean matchNode(Graph<N, E> graph, N node);
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>>
  boolean isTree(Graph<N, E> graph,
		 boolean inverted) {
    return isTree(graph, null, inverted, -1, null);
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>>
  boolean isTree(Graph<N, E> graph, 
		 boolean inverted, 
		 int edgeType) {
    return isTree(graph, null, inverted, edgeType, null);
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>>
  boolean isTree(Graph<N, E> graph, 
		 Set<N> nodeSet, 
		 boolean inverted, 
		 int edgeType) {
    return isTree(graph, nodeSet, inverted, edgeType, null);
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>>
  boolean isTree(Graph<N, E> graph, 
		 Set<N> nodeSet, 
		 boolean inverted, 
		 int edgeType, 
		 EdgePredicate<N, E> pred) {
    boolean result = false;
    int rootcount = 0;
    if (graph != null) {
      for (Iterator<N> niter = graph.nodes(); niter.hasNext();) {
	N node = niter.next();	
	if (isRoot(graph, node, nodeSet, inverted, edgeType, pred)) {
	  rootcount++;
	}
	if (rootcount > 1) {
	  return false;
	}
      }
      result = (rootcount == 1);
    }
    return result;
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>>
  boolean isLeaf(Graph<N, E> graph, 
		 N node, 
		 boolean inverted) {
    return isLeaf(graph, node, null, inverted, -1, null);
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>>
  boolean isLeaf(Graph<N, E> graph, 
		 N node, 
		 boolean inverted, 
		 int edgeType) {
    return isLeaf(graph, node, null, inverted, edgeType, null);
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>>
  boolean isLeaf(Graph<N, E> graph, 
		 N node, 
		 boolean inverted, 
		 int edgeType,
		 EdgePredicate<N, E> pred) {
    return isLeaf(graph, node, null, inverted, edgeType, pred);
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>>
  boolean isLeaf(Graph<N, E> graph, 
		 N node, 
		 Set<N> nodeSet, 
		 boolean inverted, 
		 int edgeType) {
    return isLeaf(graph, node, nodeSet, inverted, edgeType, null);
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>>
  boolean isLeaf(Graph<N, E> graph, 
		 N node, 
		 Set<N> nodeSet, 
		 boolean inverted, 
		 int edgeType,
		 EdgePredicate<N, E> pred) {
    if (graph != null) {
      if (edgeType < 0 && nodeSet == null) {
	int d;
	if (inverted) {
	  d = graph.getInDegree(node);
	} else {
	  d = graph.getOutDegree(node);
	}
	return (d == 0);
      } else {
	Set<E> edges;
	if (inverted) {
	  edges = graph.arrivingEdges(node, edgeType);
	} else {
	  edges = graph.leavingEdges(node, edgeType);
	}
	if (edges.size() == 0) {
	  return true; 
	} else if (nodeSet == null && pred == null) {
	  return false;
	} else { 
	  Iterator<E> eiter = edges.iterator(); 
	  while (eiter.hasNext()) {
	    E e = eiter.next();
	    N other; 
	    if (inverted) {
	      other = e.getSource();
	    } else {
	      other = e.getDestination();
	    }
	    if (other != null && 
		(nodeSet == null || nodeSet.contains(other)) && 
		(pred == null || pred.matchEdge(graph, e, inverted))) { 
	      return false; 
	    }
	  }
	  return true;
	}
      }
    }
    return false;
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>>
  boolean isRoot(Graph<N, E> graph, 
		 N node, 
		 boolean inverted) {
    return isRoot(graph, node, null, inverted, -1, null);
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>>
  boolean isRoot(Graph<N, E> graph, 
		 N node, 
		 boolean inverted, 
		 int edgeType) {
    return isRoot(graph, node, null, inverted, edgeType, null);
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>>
  boolean isRoot(Graph<N, E> graph, 
		 N node, 
		 Set<N> nodeSet, 
		 boolean inverted, 
		 int edgeType) {
    return isRoot(graph, node, nodeSet, inverted, edgeType, null);
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>>
  boolean isRoot(Graph<N, E> graph, 
		 N node, 
		 Set<N> nodeSet, 
		 boolean inverted, 
		 int edgeType,
		 EdgePredicate<N, E> pred) {
    if (graph != null) {
      if (edgeType < 0 && 
	  nodeSet == null) {
	int d;
	if (inverted) {
	  d = graph.getOutDegree(node);
	} else {
	  d = graph.getInDegree(node);
	}
	return (d == 0);
      } else {
	Set<E> edges;
	if (inverted) {
	  edges = graph.leavingEdges(node, edgeType);
	} else {
	  edges = graph.arrivingEdges(node, edgeType);
	}
	if (edges.size() == 0) {
	  return true; 
	} else if (nodeSet == null && pred == null) {
	  return false;
	} else { 
	  Iterator<E> eiter = edges.iterator(); 
	  while (eiter.hasNext()) {
	    E e = eiter.next();
	    N other; 
	    if (inverted) {
	      other = e.getDestination();
	    } else {
	      other = e.getSource();
	    }
	    if (other != null && 
		(nodeSet == null || nodeSet.contains(other)) && 
		(pred == null || pred.matchEdge(graph, e, inverted))) { 
	      return false; 
	    }
	  }
	  return true;
	}
      }
    }
    return false;
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>> 
  N findRoot(Graph<N, E> graph, 
	     boolean inverted, 
	     int mark) {
    return findRoot(graph, null, inverted, mark, -1, null);
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>> 
  N findRoot(Graph<N, E> graph,
	     boolean inverted, 
	     int mark, 
	     int edgeType) {
    return findRoot(graph, null, inverted, mark, edgeType, null);
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>> 
  N findRoot(Graph<N, E> graph, 
	     Set<N> nodeSet, 
	     boolean inverted, 
	     int mark, 
	     int edgeType) {
    return findRoot(graph, nodeSet, inverted, mark, edgeType, null);
  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>> 
  N findRoot(Graph<N, E> graph, 
	     Set<N> nodeSet, 
	     boolean inverted, 
	     int mark, 
	     int edgeType,
	     EdgePredicate<N, E> pred) {
    if (graph != null) {
      Iterator<N> nodes;
      if (nodeSet != null) { 
	nodes = nodeSet.iterator();
      } else { 
	nodes = graph.nodes();
      }
      List<N> nodeList = new ArrayList<N>();      
      while (nodes.hasNext()) {
	N n = nodes.next();
	nodeList.add(n); 
      }
      Collections.sort(nodeList, new DepthDegreeComparator<N,E>(graph, inverted, edgeType, pred));

      System.out.println("GraphUtilities.findRoot() nodeList: " + nodeList);
      int i = 0; 
      for (N n : nodeList) { 
	System.out.println("GraphUtilities.findRoot() nodeList[" + (i++) + "] " + 
			   n + ": maxDepth= " + getMaxDepth(graph, n, inverted, edgeType, pred));
      }
      
      for (N n : nodeList) { 
	if (!n.getMark(mark) && 
	    isRoot(graph, n, nodeSet, inverted, edgeType, pred)) {
	  return n;
	}
      }
    }
    return null;
  }

  static class DepthDegreeComparator<N extends GraphNode<E>, E extends GraphEdge<N>>
    implements Comparator<N> { 

    DepthDegreeComparator(Graph<N, E> graph, 
			  boolean inverted, 
			  int edgeType, 
			  EdgePredicate<N, E> pred) {
      this.graph = graph; 
      this.inverted = inverted;
      this.edgeType = edgeType;
      this.pred = pred; 
    }

    public int compare(N n1, N n2) {
      if (n1 != null && n2 != null) { 
	int d1, d2; 

	d1 = getMaxDepth(graph, n1, inverted, edgeType, pred);
	d2 = getMaxDepth(graph, n2, inverted, edgeType, pred);
	if (d1 != d2) { 
	  return (d2 - d1);
	}

	Set<E> edges; 
	if (inverted) {
	  edges = n1.arrivingEdges();
	} else {
	  edges = n1.leavingEdges();
	}
	d1 = 0;
	for (E e : edges) { 
	  if (matchEdgeType(edgeType, e)) 
	    d1++; 
	}
	if (inverted) {
	  edges = n2.arrivingEdges();
	} else {
	  edges = n2.leavingEdges();
	}
	d2 = 0;
	for (E e : edges) { 
	  if (matchEdgeType(edgeType, e)) 
	    d2++; 
	}
	if (d1 != d2) { 
	  return d2 - d1;
	} 

      }
      return 0;
    }

    Graph<N, E> graph;
    boolean inverted;
    int edgeType;
    EdgePredicate<N, E> pred;

  }

  static public <N extends GraphNode<E>, E extends GraphEdge<N>>
  int getMaxDepth(Graph<N, E> graph, 
		  N node, 
		  boolean inverted, 
		  int edgeType,
		  EdgePredicate<N, E> pred) {
    if (graph != null && node != null) { 
      Set<N> nodeSet = new HashSet<N>();
      nodeSet.add(node);
      return getMaxDepth(graph, node, nodeSet, inverted, edgeType, pred);
    }
    return -1; 
  }

  static private <N extends GraphNode<E>, E extends GraphEdge<N>>
  int getMaxDepth(Graph<N, E> graph, 
		  N node, 
		  Set<N> nodeSet, 
		  boolean inverted, 
		  int edgeType,
		  EdgePredicate<N, E> pred) {
    if (graph != null && node != null && nodeSet != null) { 
      int maxd = 0;
      Set<E> edges;
      if (inverted) {
	edges = graph.arrivingEdges(node, edgeType);
      } else {
	edges = graph.leavingEdges(node, edgeType);
      }
      if (edges != null && 
	  edges.size() > 0) {
	Iterator<E> subtrees = edges.iterator();
	while (subtrees.hasNext()) {
	  E e = subtrees.next();
	  N sub;
	  if (inverted) {
	    sub = e.getSource();
	  } else {
	    sub = e.getDestination();
	  }
	  if (!nodeSet.contains(sub) && 
	      (pred == null || pred.matchEdge(graph, e, inverted))) { 
	    nodeSet.add(sub); 
	    int d = getMaxDepth(graph, sub, nodeSet, inverted, edgeType, pred);
	    if (d > maxd) { 
	      maxd = d;
	    }
	    nodeSet.remove(sub);
	  }
	}
      }
      return maxd + 1;
    }
    return 0; 
  }

  public static <N extends GraphNode<E>, E extends GraphEdge<N>> 
  List<Cluster<N>> makeClusters(Graph<N, E> graph, 
				N subroot,
				boolean inverted, 
				int mark) {
    return makeClusters(graph, subroot, null, inverted, mark, -1, null, null);
  }

  public static <N extends GraphNode<E>, E extends GraphEdge<N>> 
  List<Cluster<N>> makeClusters(Graph<N, E> graph, 
				N subroot,
				boolean inverted, 
				int mark, 
				int edgeType,
				EdgePredicate<N, E> pred,
				NodePredicate<N, E> nodePred) {
    return makeClusters(graph, subroot, null, inverted, mark, edgeType, pred, nodePred);
  }

  public static <N extends GraphNode<E>, E extends GraphEdge<N>> 
  List<Cluster<N>> makeClusters(Graph<N, E> graph, 
				N subroot,
				Set<N> nodeSet, 
				boolean inverted, 
				int mark, 
				int edgeType) {
    return makeClusters(graph, subroot, nodeSet, inverted, mark, edgeType, null, null);
  }

  public static <N extends GraphNode<E>, E extends GraphEdge<N>> 
  List<Cluster<N>> makeClusters(Graph<N, E> graph, 
				N subroot,
				Set<N> nodeSet, 
				boolean inverted, 
				int mark, 
				int edgeType,
				EdgePredicate<N, E> pred,
				NodePredicate<N, E> nodePred) {
    if (graph != null) {
      List<N> nodeList = sortNodes(graph, nodeSet, inverted, mark, edgeType, pred, nodePred);
      List<Cluster<N>> clusters = new ArrayList<Cluster<N>>();

      for (N n : nodeList) { 
	if (!n.getMark(mark) && 
	    isRoot(graph, n, nodeSet, inverted, edgeType, pred)) {	  
	  Cluster<N> c = new Cluster<N>();
	  int h = getCluster(graph, n, nodeSet, c, inverted, mark, edgeType, pred);
	  c.setHeight(h);
	  c.setRoot(n);
	  clusters.add(c);	    
	}	
      }
      return clusters;
    }
    return null;
  }

  static private <N extends GraphNode<E>, E extends GraphEdge<N>> 
  List<N> sortNodes(Graph<N, E> graph, 
		    Set<N> nodeSet, 
		    boolean inverted, 
		    int mark, 
		    int edgeType,
		    EdgePredicate<N, E> pred,
		    NodePredicate<N, E> nodePred) {
    if (graph != null) {
      Iterator<N> nodes;
      if (nodeSet != null) { 
	nodes = nodeSet.iterator();
      } else { 
	nodes = graph.nodes();
      }
      List<N> nodeList = new ArrayList<N>();      
      while (nodes.hasNext()) {
	N n = nodes.next();
	if (nodePred == null || 
	    nodePred.matchNode(graph, n)) { 
	  nodeList.add(n); 
	}
      }
      Collections.sort(nodeList, new DepthDegreeComparator<N,E>(graph, inverted, edgeType, pred));
      return nodeList; 
    }
    return null;
  }

  private static <N extends GraphNode<E>, E extends GraphEdge<N>> 
  int getCluster(Graph<N, E> graph, 
		 N node, 
		 Set<N> nodeSet, 
		 Cluster<N> c,
		 boolean inverted, 
		 int mark, 
		 int edgeType,
		 EdgePredicate<N, E> pred) {
    int height = 0;
    if (node != null) { 
      if (c != null) {
	c.add(node);
      }
      node.setMark(mark, true);
      height = 1;
      Set<E> edges;
      if (inverted) {
	edges = graph.arrivingEdges(node, edgeType);
      } else {
	edges = graph.leavingEdges(node, edgeType);
      }
      if (edges != null && 
	  edges.size() > 0) {
	Iterator<E> subtrees = edges.iterator();
	int count = 0;
	while (subtrees.hasNext()) {
	  E e = subtrees.next();
	  N sub;
	  if (inverted) {
	    sub = e.getSource();
	  } else {
	    sub = e.getDestination();
	  }
	  if ((nodeSet == null || nodeSet.contains(sub)) &&
	      (pred == null || pred.matchEdge(graph, e, inverted))) { 
	    if (!sub.getMark(mark)) { 
	      int h = getCluster(graph, sub, nodeSet, c, inverted, mark, edgeType, pred);
	      if (h + 1 > height) {
		height = h + 1;
	      }
	      count += sub.getCount();
	    } else { 
	      int h = sub.getHeight();
	      if (h + 1 > height) {
		height = h + 1;
	      }
	    }
	  }
	}
	node.setCount(count + 1);
      } else {
	node.setCount(1);
      }
      node.setHeight(height);
    }
    return height;
  }

  public static <N extends GraphNode<E>, E extends GraphEdge<N>> 
  boolean isClusterLinear(Graph<N, E> graph, 
			  Cluster<N> c,
			  boolean inverted, 
			  int edgeType) { 
    return isClusterLinear(graph, c, inverted, edgeType, null);
  }

  public static <N extends GraphNode<E>, E extends GraphEdge<N>> 
  boolean isClusterLinear(Graph<N, E> graph, 
			  Cluster<N> c,
			  boolean inverted, 
			  int edgeType,
			  EdgePredicate<N, E> pred) { 
    if (graph != null && 
	c != null) { 
      N node = c.getRoot();
      while (node != null) { 
	Set<E> edges;
	if (inverted) {
	  edges = graph.arrivingEdges(node, edgeType);
	} else {
	  edges = graph.leavingEdges(node, edgeType);
	}
	if (edges != null) { 
	  Iterator<E> iter;
	  if (pred != null) { 
	    iter = edges.iterator();
	    while (iter.hasNext()) { 
	      E e = iter.next();
	      if (!pred.matchEdge(graph, e, inverted)) { 
		iter.remove();
	      }
	    }
	  }
	  int n = edges.size(); 
	  if (n == 0) { 
	    return true; 
	  } else if (n > 1) { 
	    return false;
	  }
	  // n == 1
	  iter = edges.iterator();
	  E e = iter.next();
	  if (inverted) {
	    node = e.getSource();
	  } else {
	    node = e.getDestination();
	  }
	}
      }

    }
    return false; 
  }

  /**
   * Canonicalizes the supplied string for output.
   * 
   * @param input
   *         the string to be quoted, possibly.
   * @return the input string, possibly enclosed in double quotes and with
   *         internal double quotes protected.
   */
  // essentially the agstrcanon function from libgraph (by S. J. North)
  public static String canonString(String input) {
    int len;

    if (input == null || (len = input.length()) == 0) {
      return ("\"\"");
    }

    StringBuilder strbuf = new StringBuilder(len + 8);
    char[] array = input.toCharArray();
    boolean has_special = false;

    for (int isub = 0; isub < array.length; isub++) {
      if (array[isub] == '"') {
	strbuf.append('\\');
	has_special = true;
      } else if (!has_special) {
	if (!id_char(array[isub])) {
	  has_special = true;
	}
      }
      strbuf.append(array[isub]);
    }
    // annoying, but necessary kludge to make libgraph parser happy
    if (!has_special && len <= 8) {
      String low = input.toLowerCase();
      if (low.equals("node") || 
	  low.equals("edge") || 
	  low.equals("graph") || 
	  low.equals("digraph") || 
	  low.equals("subgraph") ||
	  low.equals("strict")) {
	has_special = true;
      }
    }
    if (has_special) {
      strbuf.append('"');
      strbuf.insert(0, '"');
    }
    return (strbuf.toString());
  }

  /**
   * Check if character is a valid id character;
   * 
   * @param ch
   *   the character in question.
   */
  public static boolean id_char(char ch) {
    return ((Character.isJavaIdentifierStart(ch) && 
	     Character.getType(ch) != Character.CURRENCY_SYMBOL) || 
	    Character.isDigit(ch));
  }

}
